import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Stack;


class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    public TreeNode(int val) {
        this.val = val;
    }
}

public class Test_9_15 {

    //面试题 17.14. 最小K个数
    class intComparator implements Comparator<Integer> {
        public int compare(Integer o1, Integer o2) {
            return o2 - o1;
        }
    }

    class Solution {
        public int[] smallestK(int[] arr, int k) {
            int[] ret = new int[k];
            if(arr == null || k <= 0) return ret;

            PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(k, new intComparator());
            for(int i = 0; i < k; i++) {
                priorityQueue.offer(arr[i]);
            }
            for(int i = k; i < arr.length; i++){
                if(arr[i] < priorityQueue.peek()) {
                    priorityQueue.poll();
                    priorityQueue.offer(arr[i]);
                }
            }
            for(int i = 0; i < k; i++) {
                ret[i] = priorityQueue.poll();
            }
            return ret;
        }
    }



    //JZ36 二叉搜索树与双向链表
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null) return null;

        TreeNode head = null;
        TreeNode prevTop = null;        //记录每次弹出的结点
        Stack<TreeNode> stack = new Stack<>();
        while(pRootOfTree != null || !stack.empty()) {
            if(pRootOfTree != null) {
                stack.push(pRootOfTree);
                pRootOfTree = pRootOfTree.left;
            } else {
                TreeNode top = stack.pop();
                //第一次弹出的结点作为头结点
                if(head == null) {
                    head = top;
                }
                // 从第二次弹出结点开始，让前一次弹出结点prevTop的right域 指向 每次弹出的结点 top
                if(prevTop != null) {
                    prevTop.right = top;
                }
                top.left = prevTop;
                prevTop = top;
                pRootOfTree = top.right;

            }
        }
        return head;
    }

}
